package com.lims.algorithm.algset.linked;

import java.util.*;

/**
 * <功能简述>合并链表
 *
 * @author lims
 * @date 2020-07-23 19:33
 */
public class MergeLink {
    static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }

        @Override
        public String toString() {
            ArrayList<Integer> list = new ArrayList<>();
            Node node = this;
            while (node != null) {
                list.add(node.value);
                node = node.next;
            }
            return list.toString();
        }
    }

    /**
     * 递归合并链表(从小到大)
     * <p>
     * 1 -> 2 -> 7 -> 8 -> nil  -
     * *                         | 1 -> 2 -> 5 -> 6 -> 7 -> 8 -> nil
     * 5 -> 6 -> nil            -
     *
     * @param l1
     * @param l2
     * @return
     */
    public static Node mergeLinkRecur(Node l1, Node l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.value < l2.value) {
            l1.next = mergeLinkRecur(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeLinkRecur(l1, l2.next);
            return l2;
        }
    }

    /**
     * 循环迭代合并链表
     * *       1 -> 2 -> 7 -> 8 -> nil  -
     * *                                 | 1 -> 2 -> 5 -> 6 -> 7 -> 8 -> 9 -> nil
     * *       5 -> 6 -> 9 -> nil       -
     * ----------------------------------------------------------------------------------
     * 思想：
     * 1.先l1 、l2向后移动；
     * 2.cur找到移动后 l1、l2中最小的，用pre指向这个最小的；
     * 3.一个链表完成之后（指向null），cur/pre指向另一个剩余结点。
     * ----------------------------------------------------------------------------------
     * 算法：
     * 1.向后移动 l1 或 l2 指针；
     * 2.比较移动后l1/l2大小，有为null时，cur的next直接指向另一个链表连接剩余结点；否则移动cur指针到l1/l2中较小者；
     * 3.pre指针指向cur，回第一步循环。
     * ----------------------------------------------------------------------------------
     * l1,l2:链表头，不断移动，待比较合并的结点；
     * cur:追踪指针，追踪l1或l2中较小者；
     * pre：cur的前一个指针，用于重新next链接；
     * root：新链表头结点
     * ----------------------------------------------------------------------------------
     *
     * @param l1
     * @param l2
     */
    public static Node mergeLink(Node l1, Node l2) {
        // 新头结点
        Node root;
        // cur追踪指针的前一个结点
        Node pre;
        // 追踪指针，追踪l1/l2中的较小者
        Node cur;

        // 指针初始化
        if (l1.value <= l2.value) {
            cur = l1;
        } else {
            cur = l2;
        }
        pre = cur;
        root = cur;

        while (true) {
            // 1.向后移动 l1 / l2
            if (l1.value <= l2.value) {
                l1 = l1.next;
            } else {
                l2 = l2.next;
            }
            // 2.移动cur
            // l1为null结束时，cur.next指向l2剩余结点
            if (l1 == null) {
                cur.next = l2;
                break;
            }
            // l2为null结束时，cur.next指向l1剩余结点
            if (l2 == null) {
                cur.next = l1;
                break;
            }

            // 移动后的l1 、 l2比较大小
            if (l1.value <= l2.value) {
                cur = l1;
            } else {
                cur = l2;
            }

            // 3.pre指向cur，相当于next更新一下
            pre.next = cur;
            pre = cur;
        }
        return root;
    }

    /**
     * 从数组构建链表
     *
     * @param arr
     * @return
     */
    public static Node buildLinkFromArray(int[] arr) {
        if (arr != null && arr.length > 0) {
            Node root = new Node(-1);
            Node node = buildLinkFromArray(root, arr);
            return node.next;
        }
        return null;
    }

    /**
     * 递归构建链表
     *
     * @param root
     * @param arr
     * @return
     */
    private static Node buildLinkFromArray(Node root, int[] arr) {
        if (arr == null) {
            return null;
        }
        // 数组只剩一个时，用数组本身
        int[] nextArr = (arr.length == 1) ? arr : Arrays.copyOfRange(arr, 1, arr.length);
        // 数组只有一个时，作为最后一个结点
        root.next = (arr.length == 1) ? new Node(arr[0]) : buildLinkFromArray(new Node(arr[0]), nextArr);
        return root;
    }

    /******************************************/
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n7 = new Node(7);
        Node n8 = new Node(8);
        Node n10 = new Node(10);
        n1.next = n2;
        n2.next = n7;
        n7.next = n8;
        n8.next = n10;
        System.out.println(n1.toString());

        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n9 = new Node(9);
        n5.next = n6;
        n6.next = n9;
        System.out.println(n5.toString());

        /*Node node = mergeLinkRecur(n1, n6);
        System.out.println(node.toString());*/

        Node mergeLink = mergeLink(n1, n5);
        System.out.println("递归merge：" + mergeLink);

        int[] arr = {1, 2, 7, 8, 10};
        Node node = buildLinkFromArray(arr);
        System.out.println(node.toString());
    }
}


















